/**
 * 416. 分割等和子集
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 */

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartition(nums) {
  const { length: numsCount } = nums;
  if (numsCount < 2) {
    return false;
  }
  let sum = 0;
  let max = 0;
  for (let i = 0; i < numsCount; i += 1) {
    sum += nums[i];
    if (nums[i] > max) {
      max = nums[i];
    }
  }
  if (sum % 2 !== 0) {
    return false;
  }
  const half = sum >> 1;
  if (max > half) {
    return false;
  }
  const dp = new Array(numsCount);
  for (let i = 0; i < numsCount; i += 1) {
    dp[i] = new Array(half + 1).fill(false);
    dp[i][0] = true;
  }
  dp[0][nums[0]] = true;
  for (let i = 1; i < numsCount; i += 1) {
    for (let j = 1; j <= half; j += 1) {
      if (nums[i] > j) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] =
          dp[i - 1][j]
          || dp[i - 1][j - nums[i]];
      }
    }
  }
  return dp[numsCount - 1][half];
}

console.log(canPartition([1, 5, 11, 5]) === true);
console.log(canPartition([1, 2, 3, 5]) === false);
